import java.util.*;

public class Practice1 {
    /*
    链接https://www.nowcoder.com/practice/e160b104354649b69600803184094adb?tpId=196&tqId=40514&ru=/exam/oj
    一道排序题, 重写比较器利用堆排序或者快速排序, 然后排序判断
    end和start是否产生冲突
    从提交上看堆排序比快排要快120ms
     */
    //堆排序
    public boolean hostschedule1 (ArrayList<ArrayList<Integer>> schedule) {
        // write code here
        Time[] times = new Time[schedule.size()];
        int i = 0;
        //填写信息
        for(ArrayList<Integer> list : schedule){
            times[i++] = new Time(list.get(0),list.get(1));
        }
        //堆排序, 重写比较器
        PriorityQueue<Time> heap = new PriorityQueue<>((o1,o2) ->{
            return o1.startTime - o2.startTime;
        });
        //输入到堆
        for(int j = 0;j < i;j++){
            heap.offer(times[j]);
        }
        //判断开始和结束是否会有冲突, 注意size() > 1, 如果判空最后一次会失败
        while(heap.size() > 1){
            Time time = heap.poll();
            if(time.endTime > heap.peek().startTime){
                return false;
            }
        }
        return true;
    }
    //快速排序
    public boolean hostschedule2 (ArrayList<ArrayList<Integer>> schedule) {
        // write code here
        Time[] times = new Time[schedule.size()];
        int i = 0;
        //填写信息
        for(ArrayList<Integer> list : schedule){
            times[i++] = new Time(list.get(0),list.get(1));
        }
        Arrays.sort(times,(o1,o2) -> {
            return o1.startTime - o2.startTime;
        });
        for(int j = 0;j < i - 1;j++){
            if(times[j].endTime > times[j + 1].startTime){
                return false;
            }
        }
        return true;
    }
}
class Time{
    int startTime;
    int endTime;
    public Time(int startTime,int endTime){
        this.startTime = startTime;
        this.endTime = endTime;
    }
}